package com.lx.algorithm.Tree;


import java.io.Serializable;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-21 02:41:17
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-21     张李鑫                     1.0         1.0 Version
 */
public class Tree implements Serializable {
    static class Node<T> {
        T value;
        Node left;
        Node right;

        public Node(T value) {
            this.value = value;
        }
    }

    public static void head(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.value + " ");
        head(node.left);
        head(node.right);
    }

    public static void left(Node node) {
        if (node == null) {
            return;
        }
        left(node.left);
        System.out.println(node.value);
        left(node.right);

    }

    public static void right(Node node) {
        if (node == null) {
            return;
        }
        right(node.left);
        right(node.right);
        System.out.print(node.value + " ");
    }

    /**
     * ##############################################非递归版本
     *
     */


    /**
     * 先序遍历 头左右
     * 先直接打印第一个节点
     * 然后往栈里加东西 先加右边在加左右(先进后出 所以左边的会先出来)
     * 然后打印左边其实就等于打印了字树的头节点
     *
     * @param node
     */
    public static void headLoop(Node node) {
        if (null == node) {
            return;
        }
        Stack<Node> nodes = new Stack<>();
        nodes.add(node);
        while (!nodes.isEmpty()) {
            Node pop = nodes.pop();
            if (null != pop.right) {
                nodes.add(pop.right);
            }
            if (null != pop.left) {
                nodes.add(pop.left);
            }
            System.out.print(pop.value + " ");
        }

    }


    /**
     * 后续遍历
     * 跟先序遍历的行为是一致的
     * 但是准备两个栈
     * 先序遍历的顺序是 头左右   压栈的时候如果先压左边 顺序就变成 头右左  如果不打印放到另外一个栈里 在输出打印就是左右头
     *
     * @param node
     */
    public static void rightLoop(Node node) {
        if (null == node) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        Stack<Node> printStack = new Stack<>();
        stack.add(node);
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            printStack.add(pop);
            if (pop.left != null) {
                stack.add(pop.left);
            }
            if (pop.right != null) {
                stack.add(pop.right);
            }
        }
        while (!printStack.isEmpty()) {
            System.out.print(printStack.pop().value+" ");
        }
    }


    /**
     * <p>
     * 中序遍历 左头右
     * 用一个栈一直放左节点 因为一个树是可以拆分一个只有左节点的单链表
     * </p>
     *
     * @param cur
     * @return void
     * @Author zlx
     * @date 2021/10/16
     */
    public static void inLoop(Node cur) {
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.add(cur);
                cur = cur.left;
            } else {
                Node pop = stack.pop();
                System.out.print(pop.value + ",");
                cur = pop.right;
            }
        }
    }

    /**
     * <p>
     *    二叉树宽度优先遍历
     *    用队列 先进先出
     *    开始就把头节点加进去
     *    然后弹出一个节点有左入左有右入右
     * </p>
     * @param
     * @return void
     * @Author zlx
     * @date 2021/10/16
     */
    public static void breadth(Node node) {
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(node);
        while (!nodes.isEmpty()){
            Node poll = nodes.poll();
            System.out.print(poll.value+",");
            if (null!=poll.left){
                nodes.add(poll.left);
            }
            if (null!=poll.right){
                nodes.add(poll.right);
            }
        }

    }

    /**
     * 二叉树的序列化跟反序列化
     *
     * @param args
     */


    public static void main(String[] args) {
        Node<Integer> a = new Node<>(1);
        Node<Integer> b = new Node<>(2);
        Node<Integer> c = new Node<>(3);
        Node<Integer> d = new Node<>(4);
        Node<Integer> e = new Node<>(5);
        Node<Integer> f = new Node<>(6);
        Node<Integer> g = new Node<>(7);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
//
//        head(a);
//        headLoop(a);
//
//        System.out.println();
//        left(a);
//        System.out.println("in start");
//        inLoop(a);
//        System.out.println();
//        right(a);
//        System.out.println();
//        rightLoop(a);

        breadth(a);

        head(a);
        System.out.println();
        headLoop(a);

        System.out.println();
        left(a);
        System.out.println();
        inLoop(a);
        System.out.println();
        right(a);
        System.out.println();
        rightLoop(a);


    }
}